1. Field of the Invention
The present invention relates to a processing module, an error correction decoding circuit, and a processing method for an error locator polynomial. More particularly, it relates to a processing module in which Euclid's algorithm specialized to binary BCH code is improved and which implements Euclid's algorithm processing within an error correction decoding circuit (decoder), the error correction decoding circuit, and a processing method for an error locator polynomial.
2. Description of the Related Art
An error correction decoding circuit in optical communications is used in order that original data may be restored by correcting errors mixed with transmission degradation on an optical fiber as shown in FIG. 5 by way of example.
Error correction circuits are generally employed in the fields of communications, computers, audios/videos, etc. For the purpose of making error corrections, data need to be turned into codes, the representative ones of which are Bose-Chaudhuri-Hocquenghem (BCH) code. With the BCH code, as shown in FIG. 6 by way of example, data are inputted to a decoding circuit in the unit of one code length so as to execute a correction process.
One code length is constituted by several words, and the BCH code in which one word is of one bit as shown in FIG. 7 by way of example are called “binary BCH code” or simply the “BCH code”. Besides, the BCH code in which one word is not of one bit (one word is formed of a plurality of bits) as shown in FIG. 8 by way of example are called “non-binary BCH code” or “Reed-Solomon (RS) code”.
Both the BCH code and the RS code conform to processing rules on Galois fields. A Galois field GF (16), for example, has elements of 0, 1, α1, . . . and α14, totaling sixteen. Also the results of the additions and multiplications of these elements become any of the sixteen elements 0, 1, α1, . . . and α14, as in the addition (or subtraction) table of the Galois field GF (16) exemplified in FIG. 9 and the multiplication table thereof exemplified in FIG. 10, respectively. By way of examples, the following holds:α14+α8=α6εGF(16)  (1)α14×α8=α7εGF(16)  (2)In the case of the Galois field GF (16), the tables of the additions and multiplications become ones of 16 rows×16 columns=256 elements. By the way, in some cases, the element “0” of the Galois field is expressed as “α∞”, and the element “1” as “α0”. Besides, the subtraction of the Galois field becomes the same processing as the addition as follows:α14−α8=α14+α8εGF(16)  (3)
In the field of optical networks, the International Telecommunication Union (hereinbelow, termed “ITU-T”) formally stipulated the addition of an error correction function to an information transmission frame, in Recommendation G. 709 (Non-patent Document 1) in 2003. In Recommendation G. 709, RS code as indicated in Table 1 were first employed. The RS code conform to processing rules on a Galois field GF (256). More specifically, the Galois field GF (256) has 256 elements, and the tables of the additions and multiplications of the elements become ones of 256 rows×256 columns=65536 elements.
TABLE 1ITEMCONTENTSCode formatRS code (one word = 8 bits)One code length255 wordsProcessing rulesConforming to GF (256)Correction functionCorrectable up to 8 words
In recent years, however, transmission capacities have rapidly increased with the spread of Internet communications and the enhancements of optical fiber communication technology, and the attendant degradations of signal qualities have become serious, so that error correction codes the correction rate of which is higher than that of the RS code have been required.
Description on concatenated codes formed of two different BCH code is contained in Recommendation G. 975. 1 (Non-patent Document 2) of the ITU-T, and the concatenated codes have a correction capability higher than that of the RS code of the Galois field GF (256) indicated before. Here, the two BCH code shall be respectively written as “BCH—1” and “BCH—2” for the sake of convenience. The BCH code BCH—1 are encoded as indicated in Table 2 by way of example.
TABLE 2ITEMCONTENTSCode formatBCH code (one word = one bit)One code length3860 wordsProcessing rulesConforming to GF (4096)Correction functionCorrectable up to 3 words
Besides, the BCH code BCH—2 are encoded as indicated in Table 3.
TABLE 3ITEMCONTENTSCode formatBCH code (one word = one bit)One code length2040 wordsProcessing rulesConforming to GF (2048)Correction functionCorrectable up to 10 words
For the purpose of making efficient corrections with the concatenated codes, pluralities of identical decoding circuits need to be used in view of the characteristics of algorithms and transmission data. In the example of Recommendation G. 975. 1, as the decoding circuit of the concatenated codes, the decoding circuits of the codes BCH—1 are introduced to be in the number of 8×3=24, and those of the codes BCH—2 are introduced to be 16×3=48. A configurational example of the decoding circuit of the concatenated codes is shown in FIG. 12. The logic scale of this circuit becomes a scale of, for example, several megagates, and the capacity of memories to be mounted becomes several megabits. Considering that the logic scale of the decoding circuit of the RS code indicated in Table 1 is several tens kilogates, and that the memory capacity thereof is several tens kilobits, the logic scale of the decoding circuit of the concatenated codes in Tables 2 and 3 is very gigantic.
Further, in packaging the decoding circuit of the concatenated codes into an LSI, also the parameter of an operating frequency needs to be considered in addition to the logic scale and the memory capacity. The reason therefor is that, when the value of the operating frequency is low, a wiring delay is incurred at the high-speed operation of the LSI, so the circuit fails to operate normally.
In order to design the decoding circuit of the concatenated codes up to an actual level in view of these facts, the optimization of the decoding circuit of the BCH code becomes a very important problem. However, most of the BCH code heretofore proposed have been encoded with a small number of elements in such a Galois field as GF (16) or GF (32), and also the number of correction words of the decoding circuit has been 1 to 3 words or so. In contrast, in the above case of Table 2 or Table 3, the number of elements is large as in the Galois field GF (2048) or GF (4096), and further, as many words as 10 are corrected. In general, as the number of the elements of a Galois field becomes larger, and as the number of correctable words increases more, a decoding circuit becomes more complicated, and the logic scale of the decoding circuit enlarges more. It is the actual situation that the optimization of such a decoding circuit of the BCH code has hardly progressed as compared with that of the decoding circuit of RS code.
In this specification, JP-A-5-165662 is mentioned as Patent Document 1, and JP-A-7-240692 is mentioned as Patent Document 2.